package algorithm.dynamicProgramming.leetcode;

import java.util.Arrays;

//1014. 最佳观光组合
public class MaxScoreSightseeingPair {
    public static void main(String[] args) {
        int[] data = {8,1,5,2,6};
        System.out.println(maxScoreSightseeingPair2(data));
    }

    //暴力---超时
    public static int maxScoreSightseeingPair(int[] values) {

        int max = 0;
        for (int i = 0; i < values.length; i++) {
            for (int j =i+1;j<values.length;j++){
                max = Math.max(values[i]+values[j]+i-j,max);
            }
        }
        return max;
    }

    //动态规划
    public static int maxScoreSightseeingPair2(int[] values) {
        int[] f = new int[values.length];
        f[0] =0;
        int maxScore = Integer.MIN_VALUE;
        for (int i =1;i<values.length;i++){
            f[i] = Math.max(f[i-1],values[i-1]+i-1);
            maxScore = Math.max(maxScore,f[i]+values[i]-i);
        }
        return maxScore;
    }

    public static int maxScoreSightseeingPair3(int[] values) {
        int res = Integer.MIN_VALUE;
        int preMax = values[0]+0;
        for (int i=1;i<values.length;i++){
            res = Math.max(res,preMax+values[i]-i);
            preMax = Math.max(preMax,values[i]+i);
        }
        return res;
    }
}
